/*
 * @lc app=leetcode.cn id=4 lang=java
 *
 * [4] 寻找两个有序数组的中位数
 *
 * https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
 *
 * algorithms
 * Hard (35.86%)
 * Likes:    1413
 * Dislikes: 0
 * Total Accepted:    81.4K
 * Total Submissions: 227.1K
 * Testcase Example:  '[1,3]\n[2]'
 *
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * 
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * 
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * 
 * 示例 1:
 * 
 * nums1 = [1, 3]
 * nums2 = [2]
 * 
 * 则中位数是 2.0
 * 
 * 
 * 示例 2:
 * 
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * 
 * 则中位数是 (2 + 3)/2 = 2.5
 * 
 * 
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double middleNum = 0.0;
        int target = (nums1.length + nums2.length + 1) / 2;
        boolean even = false;//偶数
        if ((nums1.length + nums2.length) % 2 == 0) {
            even = true;
        }
        int index1 = 0;
        int index2 = 0;
        while (index1 < nums1.length || index2 < nums2.length) {
            if (index1 < nums1.length && index2 < nums2.length) {
                if (nums1[index1] <= nums2[index2]) {
                    middleNum = nums1[index1];
                    index1++;
                } else {
                    middleNum = nums2[index2];
                    index2++;
                }
            } else if (index1 < nums1.length) {
                middleNum = nums1[index1];
                index1++;
            } else if (index2 < nums2.length) {
                middleNum = nums2[index2];
                index2++;
            }
            // 中位数,当前已是下一组的下标
            if (index1 + index2 == target) {
                if (even) {
                    // 偶数
                    if (index1 < nums1.length && index2 < nums2.length) {
                        middleNum = (middleNum + (nums1[index1] <= nums2[index2] ? nums1[index1] : nums2[index2])) / 2.0;
                    } else if (index1 < nums1.length) {
                        middleNum = (middleNum + (nums1[index1])) / 2.0;
                    } else if (index2 < nums2.length) {
                        middleNum = (middleNum + (nums2[index2])) / 2.0;
                    }
                    break;
                } else {
                    break;
                }
            }
        }
        return middleNum;
    }
}

